package com.ws.demo.singleNumber;

import java.util.HashMap;
import java.util.Map;

public class SingleNumberDemo {

    /**
     * 哈希表
     * 我们可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。
     * 在统计完成后，我们遍历哈希映射即可找出只出现一次的元素。
     */
//    public int singleNumber(int[] nums) {
//        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
//        for (int num : nums) {
//            freq.put(num, freq.getOrDefault(num, 0) + 1);
//        }
//        int ans = 0;
//        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
//            int num = entry.getKey(), occ = entry.getValue();
//            if (occ == 1) {
//                ans = num;
//                break;
//            }
//        }
//        return ans;
//    }

    /**
     * 依次确定每一个二进制位
     */
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}
